package com.lzhsite.leetcode.algoritom.practise.dynamicProgramming;
/*
 题目描述
一个台阶总共有 n 级，如果一次可以跳 1 级，也可以跳 2 级。
求总共有多少总跳法，并分析算法的时间复杂度。
*/

public class 跳台阶问题 {

/*
        解法一
	首先考虑最简单的情况。如果只有 1 级台阶，那显然只有一种跳法。如果有 2 级台阶，那就有
	两种跳的方法了：一种是分两次跳，每次跳 1 级；另外一种就是一次跳 2 级。
	现在我们再来讨论一般情况。我们把 n 级台阶时的跳法看成是 n 的函数，记为 f(n)。
	 当 n>2 时，第一次跳的时候就有两种不同的选择：
	o 一是第一次只跳 1 级，此时跳法数目等于后面剩下的 n-1 级台阶的跳法数目，
	即为 f(n-1)；
	o 另外一种选择是第一次跳 2 级，此时跳法数目等于后面剩下的 n-2 级台阶的跳
	法数目，即为 f(n-2)。
	因此 n 级台阶时的不同跳法的总数 f(n)=f(n-1)+f(n-2)。
	我们把上面的分析用一个公式总结如下：
	       / 1 n = 1
	f(n)=    2 n = 2
	       \ f(n-1) + f(n-2) n > 2
	原来上述问题就是我们平常所熟知的 Fibonacci 数列问题。可编写代码，如下：
	
	那么，如果一个人上台阶可以一次上 1 个， 2 个，或者 3 个呢？这个时候，公式是这样写的：
	      / 1 n = 1
	f(n)=   2 n = 2
	        4 n = 3  
	      \ f(n-1)+f(n-2)+f(n-3) n > 3
*/
	long Fibonacci(int n) {
		int result[] = { 0, 1, 2 };
		if (n <= 2)
			return result[n];
		return Fibonacci(n - 1) + Fibonacci(n - 2);
	}

	/*
	 * 解法二 解法一用的递归的方法有许多重复计算的工作，事实上，我们可以从后往前推，一步步利用之前 计算的结果递推。 初始化时，
	 * dp[0]=dp[1]=1，然后递推计算即可： dp[n] = dp[n-1] + dp[n-2]。 参考代码如下：
	 */
	// 1, 1, 2, 3, 5, 8, 13, 21..
	int ClimbStairs(int n) {
		int dp[] = { 1, 1 };
		if (n < 2) {
			return 1;
		}
		for (int i = 2; i <= n; i++) {
			dp[2] = dp[0] + dp[1];
			dp[0] = dp[1];
			dp[1] = dp[2];
		}
		return dp[2];
	}
}
